public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // 分割
        ListNode cur = pHead;
        //两个哨兵
        ListNode Ahaed = new ListNode(0);
        ListNode Bhaed = new ListNode(0);
        ListNode A = Ahaed;
        ListNode B = Bhaed;
        while (cur != null) {
            if (cur.val < x) {
                A.next = cur;
                A = A.next;
            } else {
                B.next = cur;
                B = B.next;
            }
            cur = cur.next;
        }
        B.next = null;
        //合并
        A.next = Bhaed.next;
        pHead = Ahaed.next;
        return pHead;
    }
}